package lib

import (
	"algorithms/ds"
)

func init() {
	Probs = append(Probs, Problem{
		Num:         148,
		Discription: "不转数组的排序链表",
		Level:       2,
		Labels: map[string]int{
			"链表":   1,
			"排序":   1,
			"归并排序": 1,
			"分治":   1,
		},
	})
}

func SortList(head *ds.ListNode) *ds.ListNode {
	if head == nil || head.Next == nil {
		return head
	}

	n := 0
	temp := head
	for temp != nil {
		n++
		temp = temp.Next
	}

	preHead := &ds.ListNode{
		Next: head,
	}
	//从步长1开始，每步*2直到n-1
	for step := 1; step < n; step <<= 1 {
		leftHead := preHead.Next
		pre := preHead
		for leftHead != nil {
			//移动对应步长，得到两两合并的右半段头节点
			rightHead := moveStep(leftHead, step)
			//移动对应步长，得到下一组两两合并的左半段头节点
			nextLeftHead := moveStep(rightHead, step)
			//合并两个有序链表，同时把pre换成下一组合并链表的前一个节点
			pre = mergeList2(pre, leftHead, rightHead)
			//跳到下一组
			leftHead = nextLeftHead
		}
	}

	return preHead.Next
}

// moveStep
//
//	@param node
//	@param step
//	@return *ds.ListNode 移动对于步长后的节点，如果步长为1，返回的就是node.Next
func moveStep(node *ds.ListNode, step int) *ds.ListNode {
	for count := 0; count < step-1; count++ {
		if node == nil {
			break
		}

		node = node.Next
	}

	if node == nil || node.Next == nil {
		return nil
	}

	next := node.Next
	//注意：对于两两合并的链表要切割
	node.Next = nil

	return next
}

// mergeList2
//
//	@param pre 合并链表的前一个节点，方便连接
//	@param head1
//	@param head2
//	@return *ds.ListNode 合并链表后的最后一个节点（也是下一组合并链表的前一个节点）
func mergeList2(pre *ds.ListNode, head1 *ds.ListNode, head2 *ds.ListNode) *ds.ListNode {
	cur := pre
	for head1 != nil || head2 != nil {
		if head1 == nil {
			cur.Next = head2
			head2 = head2.Next
			cur = cur.Next
			continue
		}

		if head2 == nil {
			cur.Next = head1
			head1 = head1.Next
			cur = cur.Next
			continue
		}

		if head1.Val <= head2.Val {
			cur.Next = head1
			head1 = head1.Next
		} else {
			cur.Next = head2
			head2 = head2.Next
		}
		cur = cur.Next
	}

	return cur
}

//递归写法：和归并排序一摸一样，二分的时候注意把前半段的链表最后置为nil
/* 
func sortList(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}

	fast := head
	slow := head
	for fast.Next != nil && fast.Next.Next != nil {
		fast = fast.Next.Next
		slow = slow.Next
	}

	head2 := slow.Next
	slow.Next = nil
	sortedHead1 := sortList(head)
	sortedHead2 := sortList(head2)
	return merge(sortedHead1, sortedHead2)
}

func merge(head1, head2 *ListNode) *ListNode {
	preHead := &ListNode{}
	cur := preHead
	for head1 != nil || head2 != nil {
		if head1 == nil {
			cur.Next = head2
			head2 = head2.Next
			cur = cur.Next
			continue
		}

		if head2 == nil {
			cur.Next = head1
			head1 = head1.Next
			cur = cur.Next
			continue
		}

		if head1.Val <= head2.Val {
			cur.Next = head1
			head1 = head1.Next
		} else {
			cur.Next = head2
			head2 = head2.Next
		}
		cur = cur.Next
	}

	return preHead.Next
}
 */
